#include <iostream>

using namespace std;

struct Node {
    int Key;
    int Priority;
    int Size;
    Node* Left;
    Node* Right;

    Node(int key, int priority):Left(NULL), Right(NULL), Key(key), Priority(priority), Size(1) {}

    Node():Left(NULL), Right(NULL), Key(0), Priority(0), Size(1) {}

    Node& operator = (const Node& src){
        Key = src.Key;
        Priority = src.Priority;
        Left = src.Left;
        Right = src.Right;
    }
};

int getSize(Node* t){
    return (t == NULL) ? 0 : t->Size;
}

void calcSize(Node* t){
    t->Size = getSize(t->Left) + getSize(t->Right) + 1;
}

Node* Merge(Node* l, Node* r){
    if(l == NULL) { 
        calcSize(r);
        return r;
    }                                          // Here we haven`t both part to merge.
    if(r == NULL) {
        calcSize(l);
        return l;
    }

    if(l->Priority > r->Priority) {            // Here the root is in 'l'.
        (l->Right != NULL) ? l->Right = Merge(l->Right, r)  :  l->Right = r;
        calcSize(l);
        return l;
    }
    else {                                     // And here the root is in 'r'.
        (r->Left != NULL) ? r->Left = Merge(l, r->Left)  :  r->Left = l;
        calcSize(r);
        return r;
    }
}

void Split(Node* t, int Key, Node** l, Node** r) {
    if(t == NULL) {                            // Here we haven`t anything to split.
        *l = NULL;
        *r = NULL;
        return;
    }

    if (t->Key < Key) {                        // t will be split somewere at the right.
        *l = t;
        Split(t->Right, Key, &(*l)->Right, r);
        calcSize(*l);
    }
    else {                                     // t will be split somwere at the left.
        *r = t;
        Split(t->Left, Key, l, &(*r)->Left);
        calcSize(*r);
    }
}

void Insert(Node** t, Node* xy){
    if (*t == NULL){                        // Simple situation. 
        *t = xy;
        return;
    }
    Node* l = NULL;
    Node* r = NULL;
    Split(*t,xy->Key,&l,&r);                // In other situations to insert the object we need:
    *t = Merge(l,xy);                       // 1) Split our Treap in two speciall part.
    *t = Merge(*t,r);                       // 2) Merge three parts (partLeft + object + partRight).
    calcSize(*t);
}

void Delete(Node** t, int Key){

    Node* Tl = NULL;
    Node* Tr = NULL;                        // To delete object we split our Treap to three parts:
    Node* Tdel =  NULL;                     //        leftPart ... object ... rightPart.
    Split(*t, Key, &Tl, &Tr);               // We need to delete the object, that is why we split only:
    Split(Tr, Key+1, &Tdel, &Tr);           //              leftPart  +  rightPart.
    *t = Merge(Tl, Tr);
    calcSize(*t);
}

int getKStatistic(Node *t, int k) {
    if (t == NULL || k > getSize(t))        // Checking that k is valid.
        return NULL;
    if (k <= getSize(t->Left))              // In this part we need only to look  
        return getKStatistic(t->Left,k);    // at the number of elements from the 
    if (k > getSize(t->Left) + 1)           // right and from th left to find k-statistic.
        return getKStatistic(t->Right,k - getSize(t->Left) - 1);
    else return t->Key;
}

void print(Node* t) {                        // Ptint array using DFS.
    if (t == NULL) return;

    print(t->Left);
    cout<<t->Key<<" "<<endl;
    print(t->Right);
}

int main() {
    Node* t = NULL;

    for (int i = 0; i < 100; ++i) {
        Node* tmp = new Node(i, rand());
        Insert(&t, tmp);
    }
    print(t);
    cout<<endl;
    cout<<getKStatistic(t, 10)<<endl;

    system("pause");
    return 0;
}
